package alo.p3.work;

import alo.p3.ListNode;
import alo.p3.function1;

import java.util.ArrayDeque;

//找到链表的倒数第n个结点
public class find_n {
    //使用length方法，进行两次扫描
    ListNode find_n(ListNode headNode, int n){
        if (n<=0){
            System.out.println("n值为正整数");
        }
        function1 function1=new function1();
        int size=function1.ListLength(headNode);
        ListNode currentNode=headNode;

        if (n>size){
            System.out.println("链表中的结点个数不足");
            return null;
        }else if (n==size){
            return headNode;
        }
        else {
            while (n<size){
                currentNode=currentNode.getNext();
                size--;
            }
            return currentNode;
        }
    }


    //使用两个指针，只用一次扫描
    ListNode NthNodeFromEndListNode(ListNode headNode,int NthNode){
        ListNode pTemp=headNode,pNthNode=null;
        for (int count=1;count<NthNode;count++){
            if (pTemp!=null){
                pTemp=pTemp.getNext();
            }
        }
        while (pTemp!=null){
            if (pNthNode==null){
                pNthNode=headNode;
            }else {
                pNthNode=pNthNode.getNext();
            }
            pTemp=pTemp.getNext();

        }
        if (pNthNode!=null)
            return pNthNode;
        return null;
    }



    //使用递归的方法
    int size;

    public int kthToLast(ListNode head, int k) {
        if (head == null)
            return 0;
        int value = kthToLast(head.getNext(), k);
        if (++size == k)
            return head.getData();
        return value;
    }

    //使用栈
    public int kthToLast2(ListNode head, int k) {
        ArrayDeque<ListNode> stack = new ArrayDeque<>();
        //链表节点压栈
        while (head != null) {
            stack.push(head);
            head = head.getNext();
        }
        //在出栈串成新的链表
        ListNode firstNode = stack.pop();
        while (--k > 0) {
            ListNode temp = stack.pop();
            temp.setNext(firstNode);
            firstNode = temp;
        }
        return firstNode.getData();
    }

}
